<html lang="en">

<head>
  <meta charset="UTF-8">
  <meta http-equiv="X-UA-Compatible" content="IE=edge">
  <meta name="viewport" content="width=device-width, initial-scale=1.0">
  <title>2.三角形最小路径和</title>
</head>

<body>
  <script>
    // 动态规划
    // 因为最底层已经初始化过了，计算值要从倒数第二层开始就好
    // 当前方法会改变传入的数组
    // 自底向上
    var minimumTotal = function (triangle) {
      // dp 用最后一行表示
      const dp = triangle[triangle.length - 1]
      // 然后滚动修改dp中的数值
      for (let i = dp.length - 2; i >= 0; i--) {
        for (let j = 0; j < triangle[i].length; j++) {
          dp[j] = Math.min(dp[j], dp[j + 1]) + triangle[i][j];
        }
      }
      return dp[0]
    };
    console.log(minimumTotal([[2], [3, 4], [6, 5, 7], [4, 1, 8, 3]]))
  </script>
</body>

</html>